package net.projecteuler.prob;

public class Problem78 implements Runnable {

	private static final int MAX = 100;
	
	@Override
	public void run() {
		// initialize
		long[][] cnt = new long[MAX + 1][];
		for(int i = 0; i <= MAX; i++){
			cnt[i] = new long[i + 1];
		}
		cnt[0][0] = 1;
		
		for(int i = 1; i <= MAX; i++){
			for(int j = 1; j <= i; j++){
				int remain = i - j;
				long sum = 0;
				for(int k = 0; (k <= j) && (k <= remain); k++)
					sum += cnt[remain][k];
				cnt[i][j] = sum;// % 1000000;
			}

			long sum = 0;
			for(int j = 0; j <= i; j++)
				sum += cnt[i][j];
			System.out.println(i + " : " + sum);
			if(sum % 1000000 == 0)
				return;
		}
	}
}
